package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Sortor;

import java.util.Arrays;

public class HeapSortor implements Sortor {

	@Override
	public void sort(int[] target) {
		// 循环建堆
		for (int i = 0; i < target.length; i++) {
			// 建堆
			buildMaxHeap(target, target.length - 1 - i);
			// 交换堆顶和最后一个元素
			swap(target, 0, target.length - 1 - i);
		}
		System.out.println(Arrays.toString(target));
	}

	private void buildMaxHeap(int[] target, int lastIndex) {
		// 从lastIndex处节点（最后一个节点）的父节点开始
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// k保存正在判断的节点
			int k = i;
			// 如果当前k节点的子节点存在
			while (k * 2 + 1 <= lastIndex) {
				// k节点的左子节点的索引
				int biggerIndex = 2 * k + 1;
				// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
				if (biggerIndex < lastIndex) {
					// 若果右子节点的值较大
					if (target[biggerIndex] < target[biggerIndex + 1]) {
						// biggerIndex总是记录较大子节点的索引
						biggerIndex++;
					}
				}
				// 如果k节点的值小于其较大的子节点的值
				if (target[k] < target[biggerIndex]) {
					// 交换他们
					swap(target, k, biggerIndex);
					// 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
					k = biggerIndex;
				} else {
					break;
				}
			}
		}

	}

	private void swap(int[] target, int i, int j) {
		int tmp = target[i];
		target[i] = target[j];
		target[j] = tmp;

	}
}
